BGP ADD-PATH

The Add Path feature is described in RFC7911 – Advertisement of Multiple Paths in BGP, which defines a new BGP extension that allows a router (e.g. A route reflector) to advertise multiple paths (routes) for the same prefix. This extension allows the identification of the path using a Path Identifier, in addition to the prefix.

Why is Add Path needed?

According to RFC4271 – A Border Gateway Protocol 4 (The BGP RFC!!!): “a BGP speaker advertises to its peers only those routes that it uses itself” which means that a router that receives more than one path for the same destination, goes through the BGP decision locally, chooses the best path, and advertises only that best path to its neighbors.  In certain situations, this could cause undesirable results.

As an example, consider the following scenario:  

1. AS 100 is advertising a route for 10/8 to both R2 and R3 over AS200 and AS300
2. The route is advertised towards AS400 and accepted by R4 and R6.
3. R4 and R6 advertise the route to their route reflector (RR)
4. The RR goes through the BGP decision process itself, and choses the route from R4 as the best route.  In this example, we are assuming that we are not changing any attributes for the routes other than then next-hop, before R4 and R6 advertise the route to RR, thus RR is choosing the route via R4, based on the router-ids of R4 and R6 (lowest RID).
5. The RR then advertises the route that it selected for itself, to R5.
6. As a result, R5 only has one route to send traffic to 10/8, using R4 as the next hop.
7. R5 sends traffic towards 10/8 via R4.

This would not be a source of concern, until you realize that the link between R5 and R4 is 1Gbps, the link between R5 and R6 is 10Gbps, and the 1Gbps link towards R4 is experiencing congestion, delay, and unhappy customers!

I know, maybe you can just make that interface 10G as well, but what if you cannot do that, or you cannot do that quickly enough, or you just don’t want to!!!?!??

You might consider using local preference to solve this problem as shown:  

R6 is now advertising the route with a local preference of 300. As a result, when RR compares the two routes, the route from R6 is selected (Highest Local Preference). This route is then sent to R5, which now sends traffic destined to 10/8 via R6 (instead of R4).  This sounds great! But: what if we add another router to this picture?

The new router (R7) is physically located near R4, and you can see that the IGP metric to get to R4 is much lower than the metric to get to R6.  However, because RR is now selecting R6 as the best route, R7 will only receive this route, and will be sending traffic destined to 10/8 via R6.   “Nice!”, it looks great from R5’s perspective, but horrible from the perspective of R7.

So, what about this idea?:  What if RR sent the two routes it is receiving from R4, and R6, to both R5 and R7, and let them decide on their own which route is best, regardless of what decision he’s making for himself.

R5 now has the two routes and is comparing then and deciding that the best path to reach 10/8 is via R6.  He’s making that decision himself, and not relying on the RR, who has decided to go back to using R4, since R6 is no longer sending the route with local preference 300.  R7 is choosing R4 based on its own metrics to R4, and R6.  

Now here comes the next question:  How do I make RR send the two routes?  Yeap! “Configure ADD-PATH.” 

WHAT HAPPENS WHEN YOU ENABLE ADD PATH:

When you enable ADD PATH there are 3 major changes in the BGP behavior:

1. ADD PATH capability is negotiated
2. NLRI in BGP UPDATE is modified
3. Multiple routes are advertised

ADD PATH CAPABILITY

RFC3392 – Capabilities Advertisement with BGP-4 defines how BGP routers exchange Optional Parameters called capabilities, which as the name implies describe whether the peers are or not capable of certain functionalities, such as graceful restart, 4-byte Autonomous System numbers or Multiprotocol.  

When you enable Add Path, your BGP routers will negotiate the ADD PATH capability described in RFC7911 Section 4 , to indicate that they are capable of sending/accepting multiple paths for the same prefix.

Address family/subsequent address family could be IPv4 unicast, for example, while the Send/Receive field could have a value of:

(1) able to receive multiple paths from its peer

(2) able to send multiple paths to its peer OR

(3) able to receive and send multiple paths from/to its peer

You need to enable Add Path in both the sender and the receiver BGP peers, using the following commands:

 [edit protocols bgp group IBGP]
 ylara@vMX# set family inet unicast add-path receive  
  
 [edit protocols bgp group IBGP]
 ylara@vMX# set family inet unicast add-path send path-count <path-count>          

After you enable it on BOTH routers, you can check the logs and confirm that the routers indeed negotiated the ADD PATH.

You can also check the BGP neighbor details and again confirm ADD PATH is supported for the session:

 ylara@vMX> show bgp neighbor 192.168.5.5 | match NLRI 
 Jan 06 01:05:37
   NLRI for restart configured on peer: inet-unicast
   NLRI advertised by peer: inet-unicast
   NLRI for this session: inet-unicast
   NLRI that restart is negotiated for: inet-unicast
   NLRI of received end-of-rib markers: inet-unicast
   NLRI of all end-of-rib markers sent: inet-unicast
   NLRI's for which peer can receive multiple paths: inet-unicast
  
 ylara@vMX> show bgp neighbor 192.168.7.7 instance R5| match NLRI 
   NLRI for restart configured on peer: inet-unicast
   NLRI advertised by peer: inet-unicast
   NLRI for this session: inet-unicast
   NLRI that restart is negotiated for: inet-unicast
   NLRI of received end-of-rib markers: inet-unicast
   NLRI of all end-of-rib markers sent: inet-unicast
   NLRI's for which peer can send multiple paths: inet-unicast 

If one of the two routers does not support or it’s not configured with the add-path option, you will see something like this instead:

  ylara@vMX> show bgp neighbor 192.168.5.5 | match add 
   Options: <Preference LocalAddress Cluster AddressFamily Refresh>
   Address families configured: inet-unicast
   Local Address: 192.168.7.7 Holdtime: 90 Preference: 170
   Peer does not support Addpath    

MODIFIED NETWORK LAYER REACHABILITY INFORMATION (NLRI)

The NLRI is a variable length field that contains a list of prefixes, within the UPDATE message.

Without Add Path, the NRLI field is simply encoded as:

https://tools.ietf.org/html/rfc4271#section-4.3

With Add Path, the reachability information includes a new field (Path Identifier) and is encoded as:

https://tools.ietf.org/html/rfc7911#section-3

The Path Identifier allows sending multiple routes for the same prefix, without the receiving side assuming the second advertisement replaces the first one.

What does that mean?

Let’s take a look at our lab scenario again. 

Without the path identifier, if RR sends an update for 10/8 to R5, with next-hop = R4 and AS PATH = 200 100 I, and right after that it sends an update for the same prefix 10/8 with next-hop = R6 and AS PATH = 300 100 I, R5 will assume that the second route is a replacement for the first route (which might be the correct assumption at this point).

Let’s check the route for 10/8 on RR, what RR sent to R5, and what R5 has in its routing table for 10/8 (again with no ADD PATH configured):

 ylara@vMX# run show route 10/8 table inet.0 
 Jan 06 01:26:37
 inet.0: 17 destinations, 18 routes (17 active, 1 holddown, 0 hidden)
 + = Active Route, - = Last Active, * = Both
 10.0.0.0/8         *[BGP/170] 00:00:22, localpref 100, from 192.168.4.4
                       AS path: 200 100 I, validation-state: unverified
                     > to 172.16.7.1 via lt-0/0/0.14
                     [BGP/170] 00:00:22, localpref 100, from 192.168.6.6
                       AS path: 300 100 I, validation-state: unverified
                     > to 172.16.8.1 via lt-0/0/0.16 

RR selected the route from R4, and sent only that route to R5:

 ylara@vMX# run show route advertising-protocol bgp 192.168.5.5    
 Jan 05 22:54:40
 inet.0: 17 destinations, 18 routes (17 active, 0 holddown, 0 hidden)
   Prefix  Nexthop       MED     Lclpref    AS path
 * 10.0.0.0/8              192.168.4.4                  100        200 100 I 

Thus, R5 only has the route via R4:

 ylara@vMX# run show route 10/8 table R5.inet.0                    
 Jan 05 22:54:53
 R5.inet.0: 14 destinations, 15 routes (14 active, 0 holddown, 0 hidden)
 + = Active Route, - = Last Active, * = Both
 10.0.0.0/8         *[BGP/170] 00:00:43, localpref 100, from 192.168.7.7
                       AS path: 200 100 I, validation-state: unverified
                     > to 172.16.9.2 via lt-0/0/0.17 

Let’s change the local preference of the route being advertised by R6, so that RR changes its selection for 10/8:

 [edit policy-options policy-statement local-preference]
 ylara@vMX# set term 1 then local-preference 300 
 Jan 05 22:55:54
  
 [edit routing-instances R6 protocols bgp group IBGP]
 ylara@vMX# set export local-preference 
 Jan 05 22:57:24
  
 [edit routing-instances R6 protocols bgp group IBGP]
 ylara@vMX# commit 
 Jan 05 22:57:25
 commit complete 

After that, we check again what RR sent, and what R5 has now in its routing table:

 ylara@vMX# run show route advertising-protocol bgp 192.168.5.5    
 Jan 05 22:57:45
 inet.0: 17 destinations, 17 routes (17 active, 0 holddown, 0 hidden)
   Prefix  Nexthop       MED     Lclpref    AS path
 * 10.0.0.0/8              192.168.6.6                  300        300 100 I
  
 ylara@vMX# run show route 10/8 table R5.inet.0                       
 Jan 05 22:57:52
 R5.inet.0: 14 destinations, 15 routes (14 active, 0 holddown, 0 hidden)
 + = Active Route, - = Last Active, * = Both
 10.0.0.0/8         *[BGP/170] 00:00:26, localpref 300, from 192.168.7.7
                       AS path: 300 100 I, validation-state: unverified
                     > to 172.16.6.2 via lt-0/0/0.11 

The route was REPLACED!

You can also check the logs and confirm that R5 is treating this update for 10/8 as a “CHANGE”.

This is expected behavior. R5 is assuming that the second UPDATE message is an actual update to the previous one, which is correct. After all, that is what happened. We changed the local preference of the route advertised by R6, and RR changed his mind! 😊

Now, what if instead of RR selecting one route and sending only that route, it sent both routes. How would  R5 know the difference?

That is exactly what the path identifier solves. By adding this value to the routes, the receiver is able to treat them as separate routes, instead of one replacing the other.

As a comparison this is how the advertised routes look like with and without add-path:

SENDING MULTIPLE UPDATES:

We know that by default, a router that receives multiple BGP routes for the same destination, selects one and only one route based on BGP attributes. As we saw in the previous examples, when we enable add-path we override this behavior.

A router configured with add-path send is allowed to send all the routes known for a destination, up to a maximum number, which is part for of the configuration:

 [edit protocols bgp group IBGP]
 ylara@vMX# set family inet unicast add-path send pa? 
 Possible completions:
   path-count           Number of paths to advertise (2..6) 

This allows for the routers on the receiving side to have the ability of comparing routes by themselves and decide which route is best. 

In our test scenario, add path provides the opportunity for R5 or R7 to decide by themselves, between R4 and R6, based on their own metrics.

 [edit routing-instances R5 protocols ospf]
 ylara@vMX# run show route 10/8 table R5.inet.0 
 R5.inet.0: 14 destinations, 16 routes (14 active, 0 holddown, 0 hidden)
 + = Active Route, - = Last Active, * = Both
 10.0.0.0/8         *[BGP/170] 01:10:58, localpref 100, from 192.168.7.7
                       AS path: 300 100 I, validation-state: unverified
                     > to 172.16.6.2 via lt-0/0/0.11
                     [BGP/170] 00:00:29, localpref 100, from 192.168.7.7
                       AS path: 200 100 I, validation-state: unverified
                     > to 172.16.5.1 via lt-0/0/0.10
  
 ylara@vMX> show route 10/8 table R5.inet.0 extensive | match "Addpath|next hop|inactive|AS path"    
                 Next hop type: Indirect, Next hop index: 0
                 Next hop type: Router, Next hop index: 805
                 Next hop: 172.16.6.2 via lt-0/0/0.11, selected
                 Protocol next hop: 192.168.6.6
                 Indirect next hop: 0xba40900 1048574 INH Session ID: 0x15d
                 AS path: 300 100 I  (Originator)
                 Addpath Path ID: 1
                 Indirect next hops: 1
                         Protocol next hop: 192.168.6.6 Metric: 1
                         Indirect next hop: 0xba40900 1048574 INH Session ID: 0x15d
                         Indirect path forwarding next hops: 1
                                 Next hop type: Router
                                 Next hop: 172.16.6.2 via lt-0/0/0.11
                 Next hop type: Indirect, Next hop index: 0
                 Next hop type: Router, Next hop index: 806
                 Next hop: 172.16.5.1 via lt-0/0/0.10, selected
                 Protocol next hop: 192.168.4.4
                 Indirect next hop: 0xba41c80 1048577 INH Session ID: 0x160
                 Inactive reason: IGP metric
                 AS path: 200 100 I  (Originator)
                 Addpath Path ID: 2
                 Indirect next hops: 1
                         Protocol next hop: 192.168.4.4 Metric: 2
                         Indirect next hop: 0xba41c80 1048577 INH Session ID: 0x160
                         Indirect path forwarding next hops: 1
                                 Next hop type: Router
                                 Next hop: 172.16.5.1 via lt-0/0/0.10 

Also, if the interfaces from R5 to R4 and R6 were the same speed, we could enable load balancing on R5.

Of course, our scenario is a very simple one, because we were focusing on learning how the add path feature works, but you can apply the concept to much more complex scenarios.

Just for fun, take a look at this one:

RFC3345 – Border Gateway Protocol (BGP) Persistent Route Oscillation Condition,

and RFC7964 – Solutions for BGP Persistent Route Oscillation.

The later happens to mention RFC7911 – Advertisement of Multiple Paths in BGP (ADD PATH), as one of the solutions.

BGP